﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ClusHal
{
    class kMeans:IClusterer 
    {
        private int numClusters = 0;
        private int maxIterations = 0;
        private IDistanceMeasure distanceMeasure;
        private Action[] centroids = null;

        public kMeans(int clusters,int iterations, IDistanceMeasure measure)
        {
            numClusters = clusters;
            maxIterations = iterations;
            distanceMeasure = measure;
        }

        #region IClusterer Members

        public List<Cluster> Clusterize(List<Action> data)
        {
            int size = data[0].Size;

            Action min = DataHelper.MinAction(data);
            Action max = DataHelper.MaxAction(data);

            centroids = new Action[numClusters];
            for (int i = 0; i < numClusters; i++)
                centroids[i] = new Action(size);

            Random r = new Random(DateTime.Now.Millisecond);

            //utwórz początkowe centroidy
            for (int i = 0; i < numClusters; i++)
            {
                Action c = new Action(size);
                for (int j = 0; j < size; j++)
                {
                    //oblicz odległość między min i max
                    double d = Math.Abs(max[j] - min[j]);
                    //wylosuj wartość z tego przedziału
                    c[j] = (double)(min[j] + r.NextDouble() * d);
                }
                centroids[i] = c;
            }

            int iterations = 0;
            bool centroidsChanged = true;
            bool randomCentroids = true;

            //dopóki zmieniają się centroidy bądź nie przekroczono maksimum iteracji
            while (randomCentroids || (iterations < maxIterations && centroidsChanged))
            {
                iterations++;
                //przypisz obiekt do najbliższego centroidu
                int[] assignment = new int[data.Count];
                for (int i = 0; i < data.Count; i++)
                {
                    int tmpCluster = 0;
                    double minDistance = distanceMeasure.Distance(centroids[0], data[i]);
                    for (int j = 0; j < numClusters; j++)
                    {
                        double dist = distanceMeasure.Distance(centroids[j], data[i]);
                        if (dist < minDistance)
                        {
                            minDistance = dist;
                            tmpCluster = j;
                        }
                    }
                    assignment[i] = tmpCluster;
                }

                //przelicz pozycje centroidów
                double[,] sumPosition = new double[numClusters, size];
                int[] countPosition = new int[numClusters];

                for (int i = 0; i < data.Count; i++)
                {
                    Action a = data[i];
                    for (int j = 0; j < size; j++)
                    {
                        sumPosition[assignment[i], j] += a[j];
                    }
                    countPosition[assignment[i]]++;
                }

                centroidsChanged = false;
                randomCentroids = false;

                for (int i = 0; i < numClusters; i++)
                {
                    if (countPosition[i] > 0)
                    {
                        double[] tmp = new double[size];
                        for (int j = 0; j < size; j++)
                        {
                            tmp[j] = sumPosition[i, j] / countPosition[i];
                        }
                        Action newCentroid = new Action(tmp);
                        if (distanceMeasure.Distance(newCentroid, centroids[i]) > 0.0001)
                        {
                            centroidsChanged = true;
                            centroids[i] = newCentroid;
                        }
                    }
                    else
                    {
                        double[] randomInstance = new double[size];
                        for (int j = 0; j < size; j++)
                        {
                            double dist = Math.Abs(max[j] - min[j]);
                            randomInstance[j]=(double)(min[j]+r.NextDouble()*dist);
                        }
                        randomCentroids = true;
                        centroids[i] = new Action(randomInstance);
                    }
                }
            }

            //zapisz ostateczne clustry
            int[] clusters = new int[data.Count];
            for (int i = 0; i < data.Count; i++)
            {
                int tmpCluster = 0;
                double minDistance = distanceMeasure.Distance(centroids[0], data[i]);
                for (int j = 0; j < numClusters; j++)
                {
                    double dist = distanceMeasure.Distance(centroids[j], data[i]);
                    if (dist < minDistance)
                    {
                        minDistance = dist;
                        tmpCluster = j;
                    }
                }
                clusters[i] = tmpCluster;
            }

            //wynik
            List<Cluster> result = new List<Cluster>();
            for (int i = 0; i < numClusters; i++)
            {
                Cluster c = new Cluster();
                for (int j = 0; j < data.Count; j++)
                {
                    if (clusters[j] == i)
                    {
                        c.Actions.Add(data[j]);
                        data[j].Cluster = c;
                    }
                }
                result.Add(c);
            }
            return result;
        }

        #endregion
    }
}
